#include<bits/stdc++.h>
using namespace std;
#define maxn 9
//也可以写成 const int maxn=9; 
int a[maxn]={0,8,4,5,7,1,3,6,2};
int temp[maxn];
void merg(int l,int r,int mid){//mid表示第二个数组的开始 
	int i,j,p;//p用来控制temp数组 
	i=l,j=mid,p=l;
	while(i<mid&&j<=r){
		if(a[i]<a[j])
			temp[p++]=a[i++];
		else 
			temp[p++]=a[j++];
	}
	while(i<mid){
		temp[p++]=a[i++];
	}
	while(j<=r){
		temp[p++]=a[j++];
	}
	//将temp数组转移给原数组
	p=l,i=l;
	while(p<=r){
		a[i++]=temp[p++];
	} 
}
void merge_sort(int l,int r){
	//当左指针小于右边时，才能分 
	if(l<r){
		int mid=l+(r-l)/2;
		//分治 
		merge_sort(l,mid);
		merge_sort(mid+1,r);
		//合并
		merg(l,r,mid+1); //最后一个参数表示第二个数组的开始 
	}
	
}
int main(){
	merge_sort(1,8);
	for(int i=1;i<=8;i++){
		cout<<a[i]<<" ";
	}
	return 0;
} 